#-*- coding:utf-8 -*-
import math

def myMap(fct, seq):
	
	"""
	>>> myMap(math.sqrt, [])
	[]
	>>> myMap(math.sqrt, [2.0, 4.0, 6.0, 100.0])
	[1.4142135623730951, 2.0, 2.449489742783178, 10.0]
	>>> myMap(str.upper, list('hello'))
	['H', 'E', 'L', 'L', 'O']
	"""
	new =[]
	for i in seq:
		new.append(fct(i)) #append ne renvoie rien!
		
	return new


def myReduce(fct, seq):
	"""
	>>> myReduce(math.pow, [2, 2])
	4.0
	>>> myReduce(math.pow, [2, 3, 4])
	4096.0
	"""
	#On doit copier la liste pour ne pas massacrer le paramètre.
	cp = seq[:]
	while len(cp)>1:
		#Le 2è élém vaut ceci :
		#- seq.pop(1)
		#- seq[1]
		#On choisit ce qu'on veut, tout en sachant qu'il faut
		#quand même faire un pop pour virer l'élément 1...
		cp[0] = fct(cp[0], cp.pop(1))
	return cp[0]

def myFilter(fct, seq):
	"""
	X>>> myFilter(is_prime, range(20))
	[2, 3, 5, 7, 11, 13, 17, 19]
	>>> myFilter(str.isalpha, list('r2d2'))
	['r', 'd']
	"""
	new= []
	for i in seq:
		if fct(i):
			new.append(i)
	return new		

def prime_numbers(n):
	"""
	>>> len(prime_numbers(400))
	400
	>>> prime_numbers(15)
	[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
	"""
	tot = n #on le conserve pour la fin
	res = [2, 3] #premiers premiers
	x = 3 #dernier ajouté à la liste
	n -= 2 #nombre restant (deux précalculés)
	while n > 0:
		x += 2 #premier potentiel suivant
		#Est-ce que x est premier ?
		prime = True
		for divi in res:
			if (x % divi) == 0:
				prime = False
				break
		if prime:
			res.append(x)
			n -= 1 #un de moins à faire
	return res[:tot] #on en retourne maximum tot

def is_prime(num):
	"""
	>>> is_prime(1)
	False
	>>> is_prime(2)
	True
	>>> is_prime(3)
	True
	>>> is_prime(33)
	False
	"""
	#
	n=1
	while 1:
		t = prime_numbers(n)
		last = t.pop()
		if last > num:
			return False
		elif last == num:
			return True
		n += 1

def myInsert_naive(seq, n):
	"""
	>>> myInsert_naive(range(6), -1)
	[-1, 0, 1, 2, 3, 4, 5]
	>>> myInsert_naive(range(6), 3)
	[0, 1, 2, 3, 3, 4, 5]
	>>> myInsert_naive(range(6), 10)
	[0, 1, 2, 3, 4, 5, 10]
	"""
	#Méthode bourrine et lente, mais fonctionnelle et facile.
	idx = 0
	while idx < len(seq):
		if n < seq[idx]:
			#On l'insère...
			return seq[:idx] + [n] + seq[idx:]
		idx += 1
	#Si on arrive ici, c'est que l'élément à ajouter était plus grand
	#que tous ceux déjà présent. Il suffit de l'ajouter au bout...
	return seq + [n]

def myInsert(seq, n):
	#On considère que seq est triée dans l'ordre croissant.
	#On va donc rechercher de façon dicho la position à laquelle ajouter n
	#Une fois cette position calculée, on fait un bête insert.
	#TODO utiliser a, b, pivot et comparer au pivot.
	pass

def produit_matriciel(A, B):
	"""
	>>> produit_matriciel([[1, 2], [3, 4]], [[-2, 1], [float(3)/2, -float(1)/2]])
	[[1.0, 0.0], [0.0, 1.0]]
	>>> produit_matriciel([[2, 0, 1], [3, 6, 2]], [[1, 5], [2, 6], [3, 7]])
	[[5, 17], [21, 65]]
	>>> produit_matriciel([[1, 5], [2, 6], [3, 7]], [[2, 0, 1], [3, 6, 2]])
	[[17, 30, 11], [22, 36, 14], [27, 42, 17]]
	>>> produit_matriciel([[1.0, 2.5]], [[3.0], [4.5]])
	14.25
	>>> print produit_matriciel([[1.0, 2.5]], [[3.0, 4.5]])
	None
	>>> print produit_matriciel([[1, 5], [2, 6], [3, 7]], [[1, 5], [2, 6], [3, 7]])
	None
	"""
	
	if len(A) != len(B[0]):
		#produit impossible
		return None
	
	C = []
	for i in range(len(A)):
		#pour chaque ligne de C
		row = [] #ligne vide qu'on remplira dans le while
		for j in range(len(B[0])):
			#pour chaque colonne de C
			#on va calculer la somme (cf. énoncé)
			#et peupler la liste row
			acc = 0
			for k in range(len(B)):
				acc += A[i][k] * B[k][j]
			row += [acc] #on ajoute au bout de la ligne
		C += [row[:]] #on ajoute une copie de la ligne qu'on vient de calculer
	
	#Si on nous demandait un produit scalaire, on retourne 
	#un nombre et pas une matrice 1x1
	if len(C)==1 and len(C[0])==1:
		return C[0][0]
	
	return C

def produit_matriciel_wh(A, B):
	"""
	Calcul du produit matriciel utilisant seulement while et pas range()
	Absolument horrible à lire (mais ça fonctionnait du premier coup, donc)
	
	>>> produit_matriciel_wh([[1, 2], [3, 4]], [[-2, 1], [float(3)/2, -float(1)/2]])
	[[1.0, 0.0], [0.0, 1.0]]
	>>> produit_matriciel_wh([[2, 0, 1], [3, 6, 2]], [[1, 5], [2, 6], [3, 7]])
	[[5, 17], [21, 65]]
	>>> produit_matriciel_wh([[1, 5], [2, 6], [3, 7]], [[2, 0, 1], [3, 6, 2]])
	[[17, 30, 11], [22, 36, 14], [27, 42, 17]]
	>>> produit_matriciel_wh([[1.0, 2.5]], [[3.0], [4.5]])
	14.25
	>>> print produit_matriciel_wh([[1.0, 2.5]], [[3.0, 4.5]])
	None
	>>> print produit_matriciel_wh([[1, 5], [2, 6], [3, 7]], [[1, 5], [2, 6], [3, 7]])
	None
	"""
	if len(A) != len(B[0]):
		#produit impossible
		return None
	C = []
	i = 0 #LIGNE C
	while i < len(A):
		#pour chaque ligne de C
		row = [] #ligne vide qu'on remplira dans le while
		j = 0 #COLONNE C
		while j < len(B[0]):
			#pour chaque colonne de C
			#on va calculer la somme (cf. énoncé)
			#et peupler la liste row
			acc = 0
			k = 0
			while k < len(B):
				acc += A[i][k] * B[k][j]
				k += 1
			row += [acc] #on ajoute au bout de la ligne
			j += 1 #colonne de C suivante
		i += 1 #ligne de C suivante
		C += [row[:]] #on ajoute une copie de la ligne qu'on vient de calculer
	#Si on nous demandait un produit scalaire, on retourne 
	#un nombre et pas une matrice 1x1
	if len(C)==1 and len(C[0])==1:
		return C[0][0]
	return C

def print1(seq, separator):
	"""
	>>> print print1([1,2,3,4,5], ('[ ',' -> ',' ]'))
	[ 1 -> 2 -> 3 -> 4 -> 5 ]
	"""
	a, b, c = separator
	s = ""
	for i in seq:
		s = s + b + str(i)
	return a + s[len(b):] + c

def print2_test():
	return [[[0, 1, 2], [3, 4, 5, 6], [7, 8, 9, 10, 11]], 
			[('*******\n', '\n', '\n*******'), ('[ ',' -> ',' ]')]]

def print2(seq, seps, lvl=0):
	"""
	J'utilise étoile pour faire passer la liste retournée par print2_test
	comme la liste des paramètres à donner à print2. Tordu mais court :p
	>>> print print2(*print2_test())
	*******
	[ 0 -> 1 -> 2 ]
	[ 3 -> 4 -> 5 -> 6 ]
	[ 7 -> 8 -> 9 -> 10 -> 11 ]
	*******
	"""
	ret = ''
	if isinstance(seq, int):
		return str(seq)
	elif lvl < len(seps):
		#Si on n'est pas encore trop descendus, 
		#il nous reste des séparateurs.
		#Donc on va s'en servir...
		a, b, c = seps[lvl]
		for i in seq:
			#Appel récursif
			ret += b + print2(i, seps, lvl+1)
		return a + ret[len(b):] + c
	else:
		#On est trop descendus, on ne fait que concaténer
		for i in seq:
			ret += str(i)
		return ret

def somme_totale(mat):
	"""
	>>> somme_totale([[1,2],[3,4]])
	10
	"""
	return sum([sum(x) for x in mat]) #sumception!
	#pour chaque ligne, on fait la somme de ce qu'il y a dedans.
	#on place tout ça dans une liste et on somme son contenu à elle.

def somme_matricielle(A, B):
	"""
	>>> somme_matricielle([[1,2],[3,4]], [[1,2],[3,4]])
	[[2, 4], [6, 8]]
	>>> print somme_matricielle([[1,2],[3,4]], [[1,2],[3,4],[5,6]])
	None
	"""
	if len(A)!=len(B) or len(A[0])!=len(B[0]):
		#produit impossible
		return None
	C = A[:]
	for i in range(len(A)):
		for j in range(len(A[i])):
			#optimisation : au lieu de lire chacune séparément,
			#j'incrémente de B[i][j] le contenu d'une copie de A...
			C[i][j] += B[i][j]
	return C

import doctest
doctest.testmod()
